package com.duoduo.剑指Offer;

/**
 * @program: algorithm
 * @description: 二维数组中的查找10
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 *  
 *
 * 示例:
 *
 * 现有矩阵 matrix 如下：
 *
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 *
 * @author: chaidl  ！
 * @create: 2022-05-23 15:59
 */
public class 二维数组中的查找10 {
	/**
	 * 方法二：线性查找
	 *
	 * 由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。
	 *
	 * 从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。
	 * 如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。
	 *
	 * 可以证明这种方法不会错过目标值。如果当前元素大于目标值，
	 * 说明当前元素的下边的所有元素都一定大于目标值，因此往下查找不可能找到目标值，
	 * 往左查找可能找到目标值。如果当前元素小于目标值，说明当前元素的左边的所有元素都一定小于目标值，
	 * 因此往左查找不可能找到目标值，往下查找可能找到目标值。
	 *
	 * @param matrix
	 * @param target
	 * @return
	 */
	public boolean findNumberIn2DArray(int[][] matrix, int target) {
		if (matrix.length==0||matrix[0].length == 0||matrix==null){
			return false;
		}
		int rows = matrix.length;
		int columns = matrix[0].length;
		int row=0;
		int column=columns-1;
		while (row < rows && column >= 0){
			int num=matrix[row][column];
			if (num==target){
				return true;
			}else if (num>target){
				column--;
			}else {
				row++;
			}
		}
		return false;
	}
	/**
	 * 暴力解法
	 * @param matrix
	 * @param target
	 * @return
	 */
	public boolean findNumberIn2DArray1(int[][] matrix, int target) {
		if (matrix.length == 0 || matrix[0].length == 0 || matrix == null) {
			return false;
		}
		int length = matrix.length;
		int length1 = matrix[0].length;
		for (int i = 0; i < length; i++) {
			for (int i1 = 0; i1 < length1; i1++) {
				if (matrix[i][i1] == target) {
					return true;
				}
			}
		}
		return false;
	}
}
